# 

# 

# ### 拓扑排序（Topological Sort）详解与Python代码示例

# 

# #### 一、拓扑排序简介

# 

# 拓扑排序（Topological Sort）是对有向无环图（Directed Acyclic Graph，简称DAG）进行排序的一种算法。它将图中的节点排成一个线性序列，使得对于图中的任意一对节点u和v，如果存在一条从u到v的路径，那么在排序后的序列中，u一定出现在v的前面。这样的线性序列被称为拓扑序列。

# 

# 拓扑排序主要应用在需要确定任务执行顺序的场景中，比如编译程序的依赖关系分析、工程项目中的任务调度等。通过拓扑排序，我们可以得到一个满足所有依赖关系的任务执行顺序。

# 

# #### 二、拓扑排序的前提

# 

# 拓扑排序的前提是图必须是有向无环图（DAG）。如果图中存在环，那么就不存在满足拓扑排序要求的线性序列。因此，在进行拓扑排序之前，通常需要检测图中是否存在环。

# 

# #### 三、拓扑排序算法原理

# 

# 拓扑排序的算法原理通常基于深度优先搜索（DFS）或广度优先搜索（BFS）。这里我们以Kahn算法（基于BFS）为例进行说明。

# 

# Kahn算法的基本思路是：

# 

# 1. 从图中选择一个入度为0的节点并输出。

# 2. 从图中删除该节点和所有以它为起点的有向边。

# 3. 重复以上两步，直到当前的图为空或当前图中不存在入度为0的节点为止。如果当前图为空，则说明存在拓扑序列；否则，说明图中存在环，不存在拓扑序列。

# 

# #### 四、Python代码示例

# 

# 下面是一个基于Kahn算法的拓扑排序Python代码示例：

# 

# 

from collections import defaultdict, deque



class Graph:

    def __init__(self, vertices):

        self.graph = defaultdict(list)  # 邻接表存储图

        self.in_degree = {v: 0 for v in range(1, vertices + 1)}  # 记录每个节点的入度



    def add_edge(self, u, v):

        self.graph[u].append(v)  # 添加边<u, v>

        self.in_degree[v] += 1   # 更新节点v的入度



    def topological_sort(self):

        queue = deque()  # 使用队列存储入度为0的节点

        result = []  # 存储拓扑排序的结果



        # 将所有入度为0的节点加入队列

        for node in self.in_degree:

            if self.in_degree[node] == 0:

                queue.append(node)



        # 当队列不为空时，执行拓扑排序

        while queue:

            u = queue.popleft()  # 取出队首节点

            result.append(u)  # 将节点加入结果列表



            # 遍历节点u的所有邻居节点v

            for v in self.graph[u]:

                self.in_degree[v] -= 1  # 更新节点v的入度

                if self.in_degree[v] == 0:  # 如果节点v的入度变为0，则将其加入队列

                    queue.append(v)



        # 如果结果列表的长度等于节点数，说明存在拓扑序列；否则，图中存在环

        if len(result) == len(self.in_degree):

            return result

        else:

            return None



# 示例

g = Graph(7)

g.add_edge(1, 2)

g.add_edge(1, 3)

g.add_edge(2, 4)

g.add_edge(3, 4)

g.add_edge(4, 5)

g.add_edge(4, 6)

g.add_edge(5, 6)



topo_sort_result = g.topological_sort()

print("拓扑排序结果：", topo_sort_result)  # 输出：[1, 3, 2, 4, 5, 6]
